In our ongoing pursuit of CXCR4 antagonists as potential anticancer agents, we recently developed a potent, selective, and plasma stable peptide, Ac-Arg-Ala-[d-Cys-Arg-Phe-Phe-Cys]-COOH (3). Nevertheless, this compound was still not potent enough (IC50 ≈ 53 nM) to enter preclinical studies. Thus, a lead-optimization campaign was here undertaken to further improve the binding affinity of 3 while preserving its selectivity and proteolytic stability. Specifically, extensive structure-activity relationships (SARs) investigations were carried out on both its aromatic and disulfide forming amino acids. One among the synthesized analogue, Ac-Arg-Ala-[d-Cys-Arg-Phe-His-Pen]-COOH (19), displayed subnanomolar affinity toward CXCR4, with a marked selectivity over CXCR3 and CXCR7. NMR and molecular modeling studies disclosed the molecular bases for the binding of 19 to CXCR4 and for its improved potency compared to the lead 3. Finally, biological assays on specific cancer cell lines showed that 19 can impair CXCL12-mediated cell migration and CXCR4 internalization more efficiently than the clinically approved CXCR4 antagonist plerixafor.